package tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，
 * 使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
 * @author le
 */
public class FindErrorTreeNode
{
    public static void main(String[] args)
    {

    }

    public int[] findError (TreeNode root) {
        // write code here
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null){
            queue.offer(root);
        }
        int x = 0;
        int y = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                TreeNode tmp = queue.poll();
                if (tmp.left != null){
                    if (tmp.val < tmp.left.val){
                        x = tmp.left.val;
                    }
                    queue.offer(tmp.left);
                }

                if (tmp.right != null){
                    if (tmp.val < tmp.right.val){
                        y = tmp.left.val;
                    }
                    queue.offer(tmp.right);
                }
            }
        }
        int[] res = new int[2];
        res[0] = Math.min(x, y);
        res[1] = Math.max(x, y);
        return res;
    }
}
